๐Ÿ‘ฉโ€๐Ÿ’ป 60060. ๊ฐ€์‚ฌ ๊ฒ€์ƒ‰

@Seongukbaek Posted June 24, 2022 ยท Updated June 24, 2022 ยท 4 min read

๋ฌธ์ œ

Programmers - ๊ฐ€์‚ฌ ๊ฒ€์ƒ‰

๐Ÿ“ Logic

class Trie { private TrieNode forward; private TrieNode backward; ... }
  • ํŠธ๋ผ์ด๋ฅผ ์ •๋ฐฉํ–ฅ, ๋’ท๋ฐฉํ–ฅ์œผ๋กœ 2๊ฐœ ์ƒ์„ฑํ•œ๋‹ค.

    • ์ ‘๋‘์‚ฌ๊ฐ€ ?์ธ ๊ฒฝ์šฐ๋Š” ํƒ์ƒ‰ํ•ด์•ผ ํ•˜๋Š” ๊ฒฝ์šฐ๊ฐ€ ๋งŽ๊ณ  ์ด๋•Œ๋ฌธ์— ์‹œ๊ฐ„ ์ดˆ๊ณผ ๋ฐœ์ƒํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์ด์™€ ๊ฐ™์ด ๋‚˜๋ˆ„์–ด ์ƒ์„ฑํ•œ๋‹ค.
  • ํŠธ๋ผ์ด ๊ตฌ์กฐ๋ฅผ ๋‚˜๋ˆ„์–ด ์ €์žฅํ•˜๊ธฐ์—, ์ ‘๋‘์‚ฌ์— ๋”ฐ๋ผ ํƒ์ƒ‰ํ•˜๋Š” ํŠธ๋ผ์ด ๊ตฌ์กฐ๋ฅผ ๋ฐ”๊ฟ”๊ฐ€๋ฉฐ count๋ฅผ ๊ณ„์‚ฐํ•œ๋‹ค.

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.util.*; class TrieNode { private Map<Character, TrieNode> childNodes = new HashMap<>(); int count; // ์ž์‹ ๋…ธ๋“œ ๋งต Getter public Map<Character, TrieNode> getChildNodes() { return this.childNodes; } } class Trie { // ํŠธ๋ผ์ด๋ฅผ ์ •๋ฐฉํ–ฅ, ๋’ท๋ฐฉํ–ฅ์œผ๋กœ 2๊ฐœ ์ƒ์„ฑ // ์ ‘๋‘์‚ฌ๊ฐ€ ?์ธ ๊ฒฝ์šฐ๋Š” ํƒ์ƒ‰ํ•ด์•ผ ํ•˜๋Š” ๊ฒฝ์šฐ๊ฐ€ ๋งŽ๊ณ  ์ด๋•Œ๋ฌธ์— ์‹œ๊ฐ„ ์ดˆ๊ณผ ๋ฐœ์ƒ... private TrieNode forward; private TrieNode backward; public Trie() { forward = new TrieNode(); backward = new TrieNode(); } public void insert(String word) { insertBackward(word); insertForward(word); } // ์ฃผ์–ด์ง„ ๋ฌธ์ž์˜ ๋’ท๋ถ€๋ถ„๋ถ€ํ„ฐ Trie ๊ตฌ์กฐ ์ƒ์„ฑ, count ๊ณ„์‚ฐ private void insertBackward(String word) { TrieNode node = backward; for (int i = word.length() - 1; i >= 0; i--) { node.count++; char ch = word.charAt(i); Map<Character, TrieNode> childNodes = node.getChildNodes(); childNodes.putIfAbsent(ch, new TrieNode()); node = childNodes.get(ch); } } // ์ฃผ์–ด์ง„ ๋ฌธ์ž์˜ ์•ž๋ถ€๋ถ„๋ถ€ํ„ฐ Trie ๊ตฌ์กฐ ์ƒ์„ฑ, count ๊ณ„์‚ฐ private void insertForward(String word) { TrieNode node = forward; for (int i = 0; i < word.length(); i++) { node.count++; char ch = word.charAt(i); Map<Character, TrieNode> childNodes = node.getChildNodes(); childNodes.putIfAbsent(ch, new TrieNode()); node = childNodes.get(ch); } } // ์ ‘๋‘์‚ฌ๊ฐ€ ?๋ผ๋ฉด ๋’ท๋ฐฉํ–ฅ Trie๋กœ๋ถ€ํ„ฐ count // ๊ทธ๋ ‡์ง€ ์•Š๋‹ค๋ฉด ์ •๋ฐฉํ–ฅ Trie๋กœ๋ถ€ํ„ฐ count public int getCount(String query) { return query.charAt(0) == '?' ? getCountBackward(query) : getCountFarward(query); } private int getCountBackward(String query) { TrieNode node = backward; for (int i = query.length() - 1; i >= 0; i--) { char ch = query.charAt(i); if (ch == '?') return node.count; Map<Character, TrieNode> childNodes = node.getChildNodes(); if (!childNodes.containsKey(ch)) return 0; node = childNodes.get(ch); } return node.count; } private int getCountFarward(String query) { TrieNode node = forward; for (int i = 0; i < query.length(); i++) { char ch = query.charAt(i); if (ch == '?') return node.count; Map<Character, TrieNode> childNodes = node.getChildNodes(); if (!childNodes.containsKey(ch)) return 0; node = childNodes.get(ch); } return node.count; } } class Solution { public int[] solution(String[] words, String[] queries) { // ๋ฌธ์ž์—ด ๊ธธ์ด๋ฅผ ์ธ๋ฑ์Šค๋กœ ํ•˜๋Š” Trie ๋ฐฐ์—ด ์„ ์–ธ Trie[] trie = new Trie[100001]; int[] answer = new int[queries.length]; // ๋ฌธ์ž์—ด ๊ธธ์ด๋ฅผ ๊ธฐ์ค€์œผ๋กœ ๋ฐฐ์—ด ์ดˆ๊ธฐํ™” ํ›„, trie ์ƒ์„ฑ for (String word : words) { int len = word.length(); if (trie[len] == null) trie[len] = new Trie(); trie[len].insert(word); } // query ๊ธธ์ด์— ํ•ด๋‹นํ•˜๋Š” trie ๋ฐฐ์—ด ๊ฐ’์ด ์—†๋‹ค๋ฉด ํ•ด๋‹นํ•˜๋Š” ๋ฌธ์ž๊ฐ€ ์—†๋‹ค๋Š” ์˜๋ฏธ, // ์žˆ๋‹ค๋ฉด ๊ฐœ์ˆ˜ count for (int i = 0; i < queries.length; i++) { int len = queries[i].length(); if (trie[len] == null) answer[i] = 0; else answer[i] = trie[len].getCount(queries[i]); } return answer; } }

โœ๏ธ Review

  • ์ฒ˜์Œ์—๋Š” ์ •๊ทœ์‹์„ ์ด์šฉํ•ด์•ผํ•˜๋‚˜ ํ–ˆ์ง€๋งŒ, ํšจ์œจ์„ฑ ํ…Œ์ŠคํŠธ๊ฐ€ ์žˆ๋Š” ๊ฒƒ์œผ๋กœ ๋ณด์•„ ์ด ๋ฐฉ์‹์€ ์•„๋‹Œ ๋“ฏ ํ–ˆ๊ณ , ๊ณง๋ฐ”๋กœ Trie ๋ฅผ ์‚ฌ์šฉํ•ด์•ผ๊ฒ ๋‹ค๋Š” ์ƒ๊ฐ์ด ๋“ค์—ˆ๋‹ค.
  • ๋ชจ๋“  ๋ฌธ์ž๊ฐ€ ?์ธ ๊ฒฝ์šฐ์— ๋Œ€ํ•œ ์‹œ๊ฐ„ ์ดˆ๊ณผ๋ฅผ ํ•ด๊ฒฐํ•˜์ง€ ๋ชปํ•ด ํ’€์ด๋ฅผ ์ฐธ๊ณ ํ–ˆ๋‹ค...
@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€